import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-03-06
 * Time: 17:43
 */
public class TestHeap {
    public int [] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[10];//初始化大小
    }

    public void initElem(int[] arr){
        for (int i = 0 ; i<arr.length;i++ ){
            elem[i] = arr[i];
            usedSize++;
        }
    }
    //创建堆 十个数据 编号九 要拿到九 len -1  拿到4 -1/2
    public void createHeap(){
        for (int parent = (usedSize - 1 - 1) / 2 ;parent >=0 ;parent--){
            siftDown(parent,usedSize);
        }
    }
    //向下调整
    public void siftDown(int p , int us){
        int child = 2*p + 1;
        while (child<us) {  //us = 10 c=9
            //child 越界
            if ((elem[child+ 1]  > elem[child])) {
                child++;

            }
            if (elem[child] > elem[p]) {
                    swap(elem, child, p);

                }
        }
    }

    public void swap(int[] arr, int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //实现优先级队列
    public void offer(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = val;
        int child = usedSize;
        usedSize++;
        siftUp(child);

    }

    public boolean isFull(){
        return usedSize == elem.length;
    }
    public void siftUp2(int child) {
        int parent = (child - 1) / 2; // 父节点
        while (child > 0) { // 当 child 不是根节点时
            if (elem[child] > elem[parent]) { // 如果子节点比父节点大
                swap(elem, child, parent); // 交换
                child = parent; // 更新子节点
                parent = (child - 1) / 2; // 更新父节点
            } else {
                break; // 如果父节点比子节点大，调整结束
            }
        }
    }
    public void siftUp(int child){
        int parent = (child - 1)/2;
        while(parent >= 0) {
            if (elem[child] > elem[parent]) {
                swap(elem, child, parent);
                parent--;
                child = (child - 1)/2;
                //这里parent 和 child的移动在循环内，不应该在外面吗
            }else {
                break;
            }
        }

    }
    public void 


    class Solution {
        public int[] smallestK(int[] arr, int k) {
            PriorityQueue<Integer> pq = new PriorityQueue<>();

            if (arr == null || k == 0) {
                return new int[0];
            }

            if (k >= arr.length) {
                return arr;
            }
            for(int i = 0;i<k;i++){
                pq.offer(arr[i]);
            }
            int[] ret = new int[k];
            for(int j = k;j<arr.length;j++){
                int tmp = pq.peek();
                if(arr[j] < tmp){
                    pq.poll();
                    pq.offer(arr[j]);
                }
            }
            for(int i = 0;i<=k;i++){
                ret[i] = pq.poll();
            }
            return ret;
        }
    }
}






















